README.md

그래프

학습 목표

1. JavaScript로 그래프 구현체를 만들 수 있다

2. 그래프의 자료구조적 특성을 이해할 수 있다

3. 그래프를 활용하여 문제를 해결할 수 있다

   (그래프 내 특정한 정점, 간선, 경로 검색, 두 정점간 최단 경로, 사이클 체크)

그래프란

네트워크 구조를 추상화한 모델. 간선으로 연결된 노드의 집합이다.

• 간선으로 연결된 정점을 인접 정점이라고 한다.
  • 인접 정점의 개수를 정점의 차수라고 한다.
• 반복된 정점을 포함하지 않는 것을 단순 경로라고 한다.
• 처음과 마지막 정점이 같은 단순 경로를 사이클이라고 한다.
• 사이클이 없는 그래프를 비사이클 그래프라고 한다.
• 모든 정점간에 경로가 존재할 때 그래프가 연결되었다고 한다.
• 간선들이 한쪽으로 방향을 가진 그래프를 방향 그래프라고 한다. (반대는 무방향 그래프)
• 두 정점이 양방향 경로를 갖고 있으면 강결합되었다고 표현한다

그래프의 표현 방법

인접 행렬

가장 일반적인 표현 방법

1. 노드에 정수형의 배열 인덱스를 세팅
2. 2차원 배열의 값으로 표시

   정점간 간선이 있음을 의미[i][j] === 1

강결합이 아닌 경우 인접 행렬에는 0이 아주 많다. 따라서 메모리에 오버헤드가 발생할 수 잇다. (효과적인 방법이 아닐 확률이 높음)

인접 리스트

동적 그래프 자료 구조 표현

인접 리스트는 각 정점별로 인접 정점들을 저장한다.
(해당 데이터를 배열, 연결 리스트, 해시 맵, 딕셔너리 등 여러가지로 표현 가능)
일반적으로 인접행렬보다 순회에 유리

근접 행렬

정점을 행, 간선은 열로 표현하는 방법

두 정점을 2차원 배열로 나타낸다.

정점i가 간선j에 근접함을 의미[i][j] === 1

정점보다 간선이 많은 그래프에서 메모리 절약을 위해 사용

그래프 구현

class Graph {
  constructor(){
    this.vertices = []; // 정점
    this.adjList = new Dictionary(); // 인접리스트
  }

  // 정점 추가
  addVertex(v){
    this.vertices.push(v);
    adjList.set(v, []);
  }

  // 간선 추가
  addEdge(v, w){
    adjList.get(v).push(w);
    adjList.get(w).push(v);
  }
}